package _03_recursion;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/6/1 - 15:40
 * 递归求斐波那契数列优化 (记忆法，剪枝)
 *
 * 改进前时间复杂度  O(1.618的n次方)
 * 改进后          O(n)
 */
public class FibonacciCacheTest {
    @Test
    public void test() {
        for (int i = 0; i < 20; i++) {
            System.out.print(fibonacciCache(i) + ",");
        }
    }

    int fibonacciCache(int n) {
        if (n < 0) {
            throw new IndexOutOfBoundsException();
        }
        if (n == 0 || n == 1) {
            return n;
        }
        int[] cache = new int[n + 1];
        // 全部填充 -1
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        return foo(n, cache);
    }

    /*
     *  0    1   2   3   4   5   6   7   8   9   10  11  12     13      14
     *  0    1   1   2   3   5   8   13  21  34  55  89  144    233     377
     */
    /**
     * 带缓存递归，效率提升约 67 倍
     *
     * @param n
     * @param cache 缓存数组
     * @return
     */
    private int foo(int n, int[] cache) {
        if (cache[n] == -1) {
            cache[n] = foo(n - 1, cache) + foo(n - 2, cache);
        }
        return cache[n];
    }
}
